package ex1;

import java.util.ArrayList;


public class ParallelGameOfLife implements GameOfLife{


	/**
	 * Receives initial field, splits number and number of generations,
	 * and returns field calculated after given number of generations,
	 * in concurrent way
	 */
	public boolean[][] invoke(boolean[][] initialField, int vSplit, int hSplit,
			int generations){
		
		//no work should be done
		if(generations == 0){
			return initialField;
		}
		
		//getting dimensions of field from given array
		int fieldWidth = initialField.length;
		int fieldHeight = initialField[0].length;

		//creating maps of widths and heights of working areas of each thread,
		// just for easy creation of workers
		int workersWidth[][] = createWidthMap(fieldWidth, hSplit, vSplit);
		int workersHeight[][] = createHeightMap(fieldHeight, hSplit, vSplit);
		
		//array of objects used for waiting/notifying threads
		Synchronizer[][] synchronizersArray = createSynchronizersArray(hSplit, vSplit);
		
		//The only "global" ArrayList, used for easy access to information about
		// cells located in neighbour threads
		ArrayList<ArrayList<Cell>> cellAreas = createCellArea(synchronizersArray,
													hSplit, vSplit,
													fieldWidth,
													fieldHeight,
													workersWidth,
													workersHeight,
													initialField);

		//array of all workers (threads)
		Worker workersArray[][] = createWorkersArray(synchronizersArray,
							cellAreas, 
							hSplit, 
							vSplit,
							workersWidth, 
							workersHeight,
							generations,
							initialField);

		runAllWorkers(workersArray);

		//waiting for all workers to end their work
		joinAllWorkers(workersArray);
		
		//gathering all results of work together and returning it
		return returnAllResults(fieldWidth, fieldHeight,
								hSplit, vSplit,
								workersArray,
								workersWidth,
								workersHeight
								);
	}
	/**
	 * Asks each worker for work it done, gathers it together into
	 * one big 2D boolean array and returns it.
	 * @param width
	 * @param height
	 * @param hSplit
	 * @param vSplit
	 * @param workersArray
	 * @param workersWidth
	 * @param workersHeight
	 * @return
	 */
	boolean[][] returnAllResults(int width, int height,
								int hSplit, int vSplit,
								Worker[][] workersArray,
								int[][] workersWidth,
								int[][] workersHeight){
		//creating array
		boolean[][] finalResult = new boolean[width][];
		for(int i = 0; i < width; ++i){
			finalResult[i] = new boolean[height];
		}
		for(int x = 0; x < hSplit; ++x){
			for(int y = 0; y < vSplit; ++y){
				//each thread has it's own offset in array of results
				int offsetX = getWorkerOffsetX(x, workersWidth);
				int offsetY = getWorkerOffsetY(y, workersHeight);
				int workerFieldWidth = workersWidth[x][y];
				int workerFieldHeight = workersHeight[x][y];
				boolean[][] partOfField = workersArray[x][y].returnResult();
				for(int xCoord = 0; xCoord < workerFieldWidth; ++xCoord){
					for(int yCoord = 0; yCoord < workerFieldHeight; ++yCoord){
						finalResult[xCoord + offsetX][yCoord + offsetY] = partOfField[xCoord][yCoord];
					}
				}
			}
		}
		
		return finalResult;
	}
								
	/**
	 * Just starting all workers
	 * @param workersArray
	 */
	void runAllWorkers(Worker[][] workersArray){
		for(int x = 0; x < workersArray.length; ++x){
			for(int y = 0; y < workersArray[0].length; ++y){
				workersArray[x][y].start();
			}
		}
		return;
	}
	/**
	 * Waiting for all threads to end their work
	 * @param workersArray
	 */
	void joinAllWorkers(Worker[][] workersArray){
		for(int x = 0; x < workersArray.length; ++x){
			for(int y = 0; y < workersArray[0].length; ++y){
				try{
					workersArray[x][y].join();
				}catch(InterruptedException e){
				}
			}
		}
		return;
	}
	/**
	 * Creating array of synchronizers used for waiting/notifying threads,
	 * when they don't have work or them should be waked up
	 * @param width
	 * @param height
	 * @return
	 */
	public Synchronizer[][] createSynchronizersArray(int width, int height){
		Synchronizer[][] synchronizersArray = new Synchronizer[width][height];
		for(int x = 0; x < width; ++x){
			for(int y = 0; y < height; ++y){
				synchronizersArray[x][y] = new Synchronizer();
			}
		}
		return synchronizersArray;
	}
	
	/**
	 * Creating area of edge cells of all threads, used for getting information
	 * by thread when it needs information of cells located not in his working area
	 * Array has additional rows and columns near the edge, for comfortable use by threads
	 * Cells located on these additional edges always tell us that they are "dead"
	 * @param synchronizersArray
	 * @param hSplit
	 * @param wSplit
	 * @param width
	 * @param height
	 * @param workersWidth
	 * @param workersHeight
	 * @param initialField
	 * @return
	 */
	ArrayList<ArrayList<Cell>> createCellArea(Synchronizer[][] synchronizersArray, 
									int hSplit,
									int wSplit,
									int width,
									int height,
									int[][] workersWidth,
									int [][] workersHeight,
									boolean[][] initialField){
			//creating empty array
			//creating array with one additional row of cells near each edge,
			//there will be ZeroCell object
			int extension = 2;
			int areaWidth = width + extension;
			int areaHeight = height + extension;
			ArrayList<ArrayList<Cell>> cellsArray = new ArrayList<ArrayList<Cell>>();

			
			//filling area with cells
			for (int x = 0; x < areaWidth; ++x){
				ArrayList<Cell> currentColumn = new ArrayList<Cell>();

				//creating array row by row
				for (int y = 0; y < areaHeight; ++y){
					//creating column number x:
					//for cells located near the edge, we just create ZeroCells
					if (x == 0 || x == areaWidth - 1 || y == 0 || y == areaHeight - 1){
						currentColumn.add(new ZeroCell() );
						continue;
					}
					
					//here we add "synchronizer"s for each cell, when it is needed
					//for example, if cell located on the right edge of working area of 
					//some thread, "synchronizer" of thread located on right of this thread
					//should be added to this cell, so when cell will be updated, it will notify
					//this thread...
					//here we work only with active cells, that will be used sometimes)))
					if (isActiveCell(x, y, workersWidth, workersHeight)){
						currentColumn.add(new Cell((initialField[x-1][y-1])? 1 : 0) );
						int xCoordinate = getCellCoordinateX(x, workersWidth);
						int yCoordinate = getCellCoordinateY(y, workersHeight);
						
						boolean onTop = isCellOnTop(y, workersHeight);
						boolean onBottom = isCellOnBottom(y, workersHeight);
						boolean onRight = isCellOnRight(x, workersWidth);
						boolean onLeft = isCellOnLeft(x, workersWidth);
						
						//here we do a little magic to add needed synchronizer
						if (onTop && onRight){
							try{
								currentColumn.get(y).addSync(synchronizersArray[xCoordinate + 1][yCoordinate - 1]);
							}catch(IndexOutOfBoundsException e){}
						}
						if (onRight && onBottom){
							try{
								currentColumn.get(y).addSync(synchronizersArray[xCoordinate + 1][yCoordinate + 1]);
							}catch(IndexOutOfBoundsException e){}
						}
						if (onBottom && onLeft){
							try{
								currentColumn.get(y).addSync(synchronizersArray[xCoordinate - 1][yCoordinate + 1]);
							}catch(IndexOutOfBoundsException e){}
						}
						if (onLeft && onTop){
							try{
								currentColumn.get(y).addSync(synchronizersArray[xCoordinate - 1][yCoordinate - 1]);
							}catch(IndexOutOfBoundsException e){}
						}
						if (onTop){
							try{
								currentColumn.get(y).addSync(synchronizersArray[xCoordinate][yCoordinate - 1]);
							}catch(IndexOutOfBoundsException e){}
						}
						if (onRight){
							try{
								currentColumn.get(y).addSync(synchronizersArray[xCoordinate + 1][yCoordinate]);
							}catch(IndexOutOfBoundsException e){}
						}
						if (onBottom){
							try{
								currentColumn.get(y).addSync(synchronizersArray[xCoordinate][yCoordinate + 1]);
							}catch(IndexOutOfBoundsException e){}
						}
						if (onLeft){
							try{
								currentColumn.get(y).addSync(synchronizersArray[xCoordinate - 1][yCoordinate]);
							}catch(IndexOutOfBoundsException e){}
						}

					}else{
						//in the "holes" in array we put nulls, just for fun.
						currentColumn.add(null);
					}
				}
				cellsArray.add(currentColumn);
			}
			return cellsArray;
		}
	/**
	 * Getting coordinate of cell in the meaning of matrix of workers
	 * @param x
	 * @param workersWidth
	 * @return
	 */
	int getCellCoordinateX(int x, int[][] workersWidth){
		x = x - 1; //removing edges
		int sum = 0;
		int result = 0;
		for (int i = 0; i < workersWidth.length; ++i){
			sum += workersWidth[i][0];
			if(x < sum){
				result = i;
				break;
			}
		}
		return result;
	}
	/**
	 * Getting coordinate of cell in the meaning of matrix of workers
	 * @param y
	 * @param workersHeight
	 * @return
	 */
	int getCellCoordinateY(int y, int[][] workersHeight){
		y = y - 1;//removing edges
		int sum = 0;
		int result = 0;
		for (int i = 0; i < workersHeight[0].length; ++i){
			sum += workersHeight[0][i];
			if(y < sum){
				result =  i;
				break;
			}
		}
		return result;
	}
	/**
	 * Checks if cell located on the top of working area of thread it assigned to
	 * @param y
	 * @param workersHeight
	 * @return
	 */
	boolean isCellOnTop(int y, int[][] workersHeight){
		y = y - 1;//removing edges
		if (y == 0){
			return true;
		}
		
		int sum = 0;
		for (int i = 0; i < workersHeight[0].length; ++i){
			sum += workersHeight[0][i];
			if(y == sum){
				return true;
			}
		}
		return false;
	}
	
	/**
	 * Checks if cell located on the bottom of working area of thread it assigned to
	 * @param y
	 * @param workersHeight
	 * @return
	 */
	boolean isCellOnBottom(int y, int[][] workersHeight){
		y = y - 1;//removing edges
		int sum = 0;
		for (int i = 0; i < workersHeight[0].length; ++i){
			sum += workersHeight[0][i];
			if(y == sum - 1){
				return true;
			}
		}
		return false;
	}

	/**
	 * Checks if cell located on the left of working area of thread it assigned to
	 * @param x
	 * @param workersWidth
	 * @return
	 */
	boolean isCellOnLeft(int x, int[][] workersWidth){
		x = x - 1;//removing edges
		if (x == 0){
			return true;
		}
		
		int sum = 0;
		for (int i = 0; i < workersWidth.length; ++i){
			sum += workersWidth[i][0];
			if(x == sum){
				return true;
			}
		}
		return false;
	}
	
	/**
	 * Checks if cell located on the right of working area of thread it assigned to
	 * @param x
	 * @param workersWidth
	 * @return
	 */
	boolean isCellOnRight(int x, int[][] workersWidth){
		x = x - 1;//removing edges
		int sum = 0;
		for (int i = 0; i < workersWidth.length; ++i){
			sum += workersWidth[i][0];
			if(x == sum - 1){
				return true;
			}
		}
		return false;
	}
	
	/**
	 * Checking if cell is located on the edge of an working area of some thread
	 * @param x
	 * @param y
	 * @param workersWidth
	 * @param workersHeight
	 * @return
	 */
	boolean isActiveCell(int x, int y, int[][] workersWidth, int[][] workersHeight){
		x = x - 1;//removing edges
		y = y - 1;//removing edges
		
		//1. checking if cell located on "horizontal edge"
		if (y == 0){
			return true;
		}
		//
		int sumY = 0;
		for (int i = 0; i < workersHeight[0].length; ++i){
			sumY += workersHeight[0][i]; //row i of first column, all columns are same
			//if y = sumY then it is located on the next "worker's field", 
			// if y = sumY - 1 then it is located on current worker's field;
			if ( y == sumY || y == sumY - 1){
				return true;
			}
		}
		
		//2. checking if cell located on "horizontal edge"
		if (x == 0){
			return true;
		}
		
		int sumX = 0;
		for (int i = 0; i < workersWidth.length; ++i){
			sumX += workersWidth[i][0]; //first row of column 'i' , all rows are same
			if ( x == sumX || x == sumX - 1){
				return true;
			}
		}
		return false;
	}
	
	/**
	 * Returns coordinates of top left edge cell of an worker in cellsArea
	 * @param workerX
	 * @param workersWidth
	 * @return
	 */
	int getWorkerOffsetX(int workerX, int[][] workersWidth){
		int x = 0;
		for (int i = 0; i < workerX; ++i){
			x += workersWidth[i][0];
		}
		return x;
	}
	/**
	 * Returns coordinates of top left edge cell of an worker in cellsArea
	 * @param workerY
	 * @param workersHeight
	 * @return
	 */
	int getWorkerOffsetY(int workerY, int[][] workersHeight){
		int y = 0;
		for (int i = 0; i < workerY; ++i){
			y += workersHeight[0][i];
		}
		return y;
	}
	
	/**
	 * Returns 2d array of sizes of working area of threads
	 * @param fieldWidth
	 * @param hSplit
	 * @param vSplit
	 * @return
	 */
	int[][] createWidthMap(int fieldWidth, int hSplit, int vSplit){
		int[][] workersWidth = new int[hSplit][];
		for(int i = 0; i < hSplit; ++i){
			workersWidth[i] = new int[vSplit];
		}
		int workerFieldWidth = fieldWidth/hSplit; //div of integers
		int workerFieldWidthLast = workerFieldWidth + fieldWidth%hSplit;
		for(int x = 0; x < hSplit; ++x){
			for(int y = 0; y < vSplit; ++y){
				workersWidth[x][y] = (x == hSplit - 1) ? workerFieldWidthLast : workerFieldWidth;
			}
		}
		return workersWidth;
	}
	
	/**
	 * Returns 2d array of sizes of working area of threads
	 * @param fieldHeight
	 * @param hSplit
	 * @param vSplit
	 * @return
	 */
	int[][] createHeightMap(int fieldHeight, int hSplit, int vSplit){
		int[][] workersHeight = new int[hSplit][];
		for(int i = 0; i < hSplit; ++i){
			workersHeight[i] = new int[vSplit];
		}
		int workerFieldHeight = fieldHeight/vSplit; //div of integers
		int workerFieldHeightLast = workerFieldHeight + fieldHeight%vSplit;

		for(int x = 0; x < hSplit; ++x){
			for(int y = 0; y < vSplit; ++y){
				workersHeight[x][y] = (y == vSplit - 1) ? workerFieldHeightLast : workerFieldHeight;
			}
		}	
		return workersHeight;
	}
	
	
	//for achieving better performance and avoiding stalls
	;
	
	/**
	 * Creating 2D array of workers with all data calculated before
	 * @param synchronizersArray
	 * @param commonCellsArea
	 * @param width
	 * @param height
	 * @param workersWidth
	 * @param workersHeight
	 * @param generations
	 * @param initialField
	 * @return
	 */
	Worker[][] createWorkersArray(Synchronizer[][] synchronizersArray,
			ArrayList<ArrayList<Cell>> commonCellsArea, int width, int height,
						int[][] workersWidth, int[][] workersHeight, int generations,
						boolean[][] initialField){
		Worker[][] workersArray = new Worker[width][height];
		for(int x = 0; x < width; ++x){
			for(int y = 0; y < height; ++ y){
				//copying working area of thread from given array
				boolean[][] partOfField = copyPartOfField(initialField, 
											getWorkerOffsetX(x, workersWidth),
											getWorkerOffsetY(y, workersHeight),
											workersWidth[x][y], workersHeight[x][y]);
				workersArray[x][y] = new Worker(partOfField,
								commonCellsArea, getWorkerOffsetX(x, workersWidth), 
								getWorkerOffsetY(y, workersHeight), 
								generations, synchronizersArray[x][y]);
			}
		}
		return workersArray;
	}
	
	/**
	 * Copying part of field from big array for creating working area for worker
	 * @param initialField
	 * @param offsetX
	 * @param offsetY
	 * @param width
	 * @param height
	 * @return
	 */
	boolean[][] copyPartOfField(boolean[][] initialField,
										int offsetX, int offsetY, 
										int width, int height){
		boolean[][] partOfField = new boolean[width][];
		for(int i = 0; i < width; ++i){
			partOfField[i] = new boolean[height];
		}
		for(int x = 0; x < width; ++x){
			for(int y = 0; y < height; ++y){
				partOfField[x][y] = initialField[x + offsetX][y + offsetY];
			}
		}
		return partOfField;
	}
}

